/*Group 04
Jose Renato da Silva Bonatelli 7288964
Matheus Martins Teixeira 7277482
Rafael de Paula Pinto Paravia 71522567*/

/*Given a graph, calculates the length of the diameter of a minimum diameter spanning tree with a parallel approach using MPI*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define INF (1<<29)
#define MIN( a , b ) ( (a<b) ? (a) : (b) )
#define EPS 1E-10
#define MAXV 1005
#include "mpi.h"
#include <stddef.h>

typedef struct str
{
    int duw;
    int dvw;
    int w;
} str;

typedef struct edge
{
    int u;
    int v;
} edge;

int cmp(const void * a, const void * b)  /*Comparison function*/
{
    if(((str*)a)->duw != ((str*)b)->duw) return ( ((str*)a)->duw < ((str*)b)->duw );
    else return ( ((str*)a)->dvw < ((str*)b)->dvw );
}
edge edges[(MAXV*(MAXV-1))>>1 ]; /*Vector of edges*/
int adj[MAXV][MAXV]; /*Adjacenty Matrix*/
int dist[MAXV][MAXV]; /*Minimal Distance Matrix (after Floyd Warshall)*/

int main (int argc, char* argv[])
{
    int i,j,k,n,m;
    int u,v;
    double minAnsw=INF;
    double answ=INF;

    memset(adj, 0, sizeof(int) * MAXV * MAXV); /*Initializating matrix adj*/

    int noProcesses, /*Number of processes*/
        processId; /*Rank of the calling process*/

    MPI_Status status;
    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&processId);
    MPI_Comm_size(MPI_COMM_WORLD,&noProcesses);

    /*Create a type for struct edge*/
    const int nitems=2;
    int blocklengths[2] = {1,1};
    MPI_Datatype types[2] = {MPI_INT, MPI_INT};
    MPI_Datatype mpi_edge_type;
    MPI_Aint offsets[2];

    offsets[0] = offsetof(edge, u);
    offsets[1] = offsetof(edge, v);

    MPI_Type_create_struct(nitems, blocklengths, offsets, types, &mpi_edge_type);
    MPI_Type_commit(&mpi_edge_type);

    /*Master*/
    if (processId == 0)
    {
        scanf(" %d %d ",&n,&m);/*Reading the number of joints and streets(vertexes,edges)*/
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
            {
                if(i!=j)dist[i][j]=INF; /*Distance of vertex i to j = "infinity"*/
                else dist[i][j] = 0; /*Distance of vertex i to i = 0*/
            }


        /*Reading input*/
        for(k=0; k<m; k++) /*For all edges*/
        {
            scanf(" %d %d ",&i,&j); /*Edge(i,j)*/
            i--;
            j--; /*Starting at position zero instead of one*/
            edges[k].u=i;
            edges[k].v=j; /*Saving the edge*/
            scanf(" %d ",&adj[i][j]); /*Reading weight(i,j)*/
            dist[j][i] = dist[i][j] = adj[j][i] = adj[i][j];
        }
        /*Floyd Warshall Algorithm*/
        for(k=0; k<n; k++)
            for(i=0; i<n; i++)
                for(j=0; j<n; j++)
                    dist[i][j] = MIN ( dist[i][j], dist[i][k] + dist[k][j]);
            /*dist[i][j] now has the minimum distance from each vertex to each vertex*/

    }
    /*Broadcasting the info to everyone else*/
    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Bcast(&m, 1, MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Bcast(&dist, MAXV*MAXV, MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Bcast(&adj, MAXV*MAXV, MPI_INT, 0, MPI_COMM_WORLD);
    MPI_Bcast(&edges, (MAXV*(MAXV-1))>>1, mpi_edge_type, 0, MPI_COMM_WORLD);

    /*Workers*/
    if (processId > 0)
    {
        int w,u,v,i1,i2; /*Iterators*/
        str s[MAXV];
        double Ey = INF;
        double upper_bound,lower_bound,f1,f2,mean;/*Variables for binary search*/

        /*Each process calculates a fraction of the total value*/
        unsigned int begin = (processId-1)*m/(noProcesses-1);
        unsigned int end = ((processId-1))==(noProcesses-2)?m:(processId)*m/(noProcesses-1);

        /*Running over all the edges (u,v)*/
        for(k=begin; k<end; k++)
        {
            u = edges[k].u;
            v = edges[k].v;
            Ey = INF;
            /*Phase One*/
            /*Getting the minimum distance from vertexes u and v to all vertexes w*/
            for(w=0; w<n; w++)
            {
                s[w].duw = dist[u][w];
                s[w].dvw = dist[v][w];
                s[w].w = w;
            }
            qsort(s,n,sizeof(str),cmp); /*Ordering s*/
            /*Phase Two*/
            i1 = 0;
            i2 = 1;
            while(i2 < n )
            {
                if(s[i1].dvw > s[i2].dvw)
                {
                    i2++;
                    continue;
                }
                /*Binary Search to find mean*/
                upper_bound = adj[u][v];
                lower_bound = 0.0;
                while(fabs(upper_bound-lower_bound)>EPS)
                {
                    mean = (upper_bound+lower_bound)/2.0;
                    f1 = fmin( mean + s[i1].duw , adj[u][v] - mean + s[i1].dvw);
                    f2 = fmin( mean + s[i2].duw , adj[u][v] - mean + s[i2].dvw);
                    if(f1>f2) lower_bound = mean;
                    else upper_bound = mean;
                }
                /*By the end of the loop, mean is the absolute center of edge(u,v)(guessing hospital location)
                and f1=f2=distance from the hospital to the vertex w*/
                i1 = i2;
                i2++;
                if(f1<Ey)Ey = f1;/*Updating Ey if the distance was optimized*/
            }
            /*The answer is the biggest distance of a vertex w to the best location of the hospital*/
            if(answ>Ey)
            {
                answ = Ey;
            }
        }
    }
    /*Reducing values on all processes to a single value*/
    MPI_Reduce(&answ, &minAnsw, 1, MPI_DOUBLE, MPI_MIN, 0, MPI_COMM_WORLD);
    if (processId == 0) printf("%g\n", minAnsw);/*Output*/

    MPI_Type_free(&mpi_edge_type);
    MPI_Finalize();

    return 0;
}

